package com.rankeiot.platform.util;

/**
 * 循环队列： 先进先出
 *        队列同样是个概念上的辅助工具。这里采用数组完成队列的操作，仍然采用泛型
 *        队列的数据项的入队、出队时间复杂度为常数 O(1)。
 *        通过队头队尾指针的移动保存所有数据位置不动，而不是移动数据项。
 *        在这里，数组的大小比队列存放数据元素大1，主要是为了方便队满的判断。
 */
public class Queue<T> {

	private int maxSize;   // 队列最多容纳数量
	private Object[] queueArray;
	private int front;   // 队头
	private int rear;	// 队尾
	private int size;

	public Queue(int length) {
		maxSize = length;
		queueArray = new Object[maxSize];
		front = 0;
		rear = -1;
		size = 0;
	}

	/**	入队： 先将rear(队为指针) 加1， 后将数据项存入rear的位置。
	 *	当rear 指向maxSize -1 的位置时，将rear 设置为-1（循环队列），加1 后存入数据项。
	 */
	public void enQueue(T str){

		if(isFull()){    // 入队之前先检查队列是否已满，已满则抛出异常。
			deQueue();//throw new RuntimeException("队列已满，" + str + " 不能入队！");
		}

		if(rear == maxSize -1){
			rear = -1;
		}
		queueArray[++rear] = str;  // 先将 rear 加1，后取值
		size++;
	}


	/**出队： 先取出front 的值，然后将front 减1
	 * 如果 front 超过了数组的顶端，将 front 设置为 0（循环队列）
	 */
	@SuppressWarnings("unchecked")
	public T deQueue(){

		if(isEmpty()){   // 出队之前先检查队列是否为空， 为空则抛出异常。
				throw new RuntimeException("队列为空，不能出队！");
		}

		T str = (T) queueArray[front++];  // 先去 queueArray[front] 的值，后将front 加1
		if(front == maxSize){
			front = 0;
		}
		size--;
		return str;
	}
	/**
	 * 得到最先进来的
	 */
	@SuppressWarnings("unchecked")
	public T getFirstQueue(){
		if(isEmpty()){
			throw new RuntimeException("队列为空，不能出队！");
		}
		T str = (T) queueArray[front];
		return str;
	}
	/**
	 * 得到最后进来的
	 */
	@SuppressWarnings("unchecked")
	public T getLastQueue(){
		if(isEmpty()){
			throw new RuntimeException("队列为空，不能出队！");
		}
		T str = (T) queueArray[rear];
		return str;
	}
	/**查看对头数据项
	 */
	@SuppressWarnings("unchecked")
	public T peek(){
		if(isEmpty()){   // 查看队头时，判断是否为空， 为空则抛出异常。
				throw new RuntimeException("队列为空！");
		}
		return (T) queueArray[front];
	}

	/** 判断队列是否为空。队空： rear + 1 = front 或 front + maxSize -1 = rear
	 *  通过数组容量比队列数据项的最大值大一，来区分对空和对满。
	 */
	public boolean isEmpty(){
		return (rear + 1 == front || front + maxSize -1 == rear);
	}

	 /**判断队列是否为满。 队满： rear + 2 = front 或 front + maxSize -2 = rear
	  * 通过数组容量比队列数据项的最大值大一，来区分对空和对满。
	  */
	public boolean isFull(){
		return (rear + 2 == front || front + maxSize -2 == rear);
	}

	/** 获取队列的大小
	 */
	public int queueSize(){
	/* 可以通过队头队尾计算出队列的大小，也可以通过一个计数器，当入队是加1，出队是减1.
	 if(rear >= front){
			return rear - front +1;
		}else {
			return maxSize - front + (rear + 1);
		}
	*/
		return size;
	}

}
